1. Field of the Invention
The present invention relates to an apparatus for correcting errors present in stored or transmitted data; and, more particularly, to an apparatus for evaluating an error evaluator polynomial, an error locator polynomial and a differential polynomial which are used in correcting errors in the data encoded by using an algebraic code, such as a Reed-Solomon code.
2. Description of Related Art
Noise occurring during a process of transmitting, storing or retrieving data can in turn cause errors in the transmitted, stored or retrieved data. Accordingly, various encoding techniques, having the capability of rectifying such errors, for encoding the data to be transmitted or stored have been developed.
In such encoding techniques, a set of check bits is appended to a group of message or information bits to form a codeword. The check bits, which are determined by an encoder, are used to detect and correct the errors. In this regard, the encoder essentially treats the bits comprising the message bits as coefficients of a binary message polynomial and derives the check bits by multiplying the message polynomial R(x) with a code generator polynomial G(x) or dividing R(x) by G(x), to thereby provide a codeword polynomial C(x). The code generator polynomial is selected to impart desired properties to a codeword upon which it operates so that the codeword will belong to a particular class of error-correcting binary group codes (see, e.g., S. Lin et al., xe2x80x9cError Control Coding: Fundamentals and Applicationsxe2x80x9d, Prentice-Hall, 1983).
One class of error correcting codes is the well-known BCH (Bose-Chaudhuri-Hocquenghen) codes, which include the Reed-Solomon (xe2x80x9cRSxe2x80x9d) code. The mathematical basis of the RS code is explained in, e.g., the aforementioned reference by Lin et al. and also in Berlekamp, xe2x80x9cAlgebraic Coding Theoryxe2x80x9d, McGraw-Hill, 1968, which is further referred to in U.S. Pat. No. 4,162,480 issued to Berlekamp. The aforementioned references are hereby incorporated by reference in pertinent part.
The invention herein provides a method and apparatus for decoding an algebraic-coded message. The method can include the steps of determining a discrepancy indicator, with the discrepancy being between a calculated and a predicted value; determining an error locator polynomial using a selected class of error correction algorithms, such as, for example, a Berlekamp-Massey algorithm; and detecting an uncorrectable message using the selected error correction algorithm. The apparatus is composed of storage devices which can include recirculating storage devices; arithmetic components attached to the storage devices, the components operating over a Galois Field on selected contents of the storage devices; and an uncorrectable message detector, connected with the storage devices and the arithmetic components.